《剑指offer》 06.从尾到头打印链表

剑指offer
留言

note: insert方法虽然好写但是时间复杂度一般很高，反转链表虽然不错但是需要问清楚是否可以改动原链表

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

1
2
输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

解法一： vector的insert方法

思路

vector容器类定义了insert方法，可以在任意位置插入元素。显然我们可以在遍历链表时，把每个元素插入最前面。就能得到反转的链表的数值了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        while(head!=NULL){
            ans.insert(ans.begin(),head->val);
            head = head->next;
        }
        return ans;
    }
};

复杂度

  • 时间复杂度$O(n)$。实际上vector容器insert函数在STL中的实现是每次插入时，将插入位置后的东西整体向后挪动，再在空的位置放入元素，实际时间是非常多的。
  • 空间复杂度$O(1)$。没有额外使用空间

解法二：使用栈

思路

对于链表、反转关键字，其实很容易想到栈这一数据结构，利用其先进后出的特性，我们遍历链表时进行入栈，完毕后边出栈边存入数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        stack<int> stk;
        while(head!=NULL){
            stk.push(head->val);
            head = head->next;
        }
        while(!stk.empty()){
            ans.push_back(stk.top());
            stk.pop();
        }
        return ans;
    }
};

复杂度

  • 时间复杂度$O(n)$。遍历了链表和栈，依然是$O(n)$级别
  • 空间复杂度$O(n)$。额外使用了栈空间。

解法三： 链表反转

思路

在链表相关专题中，一般会要求我们不适用额外空间，那一般我们使用的方法就是直接的链表反转。链表反转都是通过一个指向前一个结点的指针、一个临时节点来达到目的。 注意的是需要提前问清楚链表是否可以更改！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        ListNode* pre = NULL;
        ListNode* temp = NULL;
        while(head!=NULL){
            temp = head->next;
            head->next = pre;
            pre = head;
            head = temp;
        }

        while(pre!=NULL){
            ans.push_back(pre->val);
            pre = pre->next;
        }
        
        
        return ans;
    }
};

复杂度

  • 时间复杂度$O(n)$。遍历两次链表
  • 空间复杂度$O(1)$。没有使用额外空间

解法四：反转数组

思路

既然链表可以反转，那么数组必然也可以反转，甚至写起来更简单

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        
        while(head!=NULL){
            ans.push_back(head->val);
            head = head->next;
        }

        reverse(ans.begin(),ans.end());
       
        return ans;
    }
};

复杂度

  • 时间复杂度$O(n)$。遍历链表。
  • 空间复杂度$O(1)$。不需要额外空间。